package top.hkyzf.study.leetcode.tree;

import org.junit.Test;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @author 朱峰
 * @date 2022-2-23 12:21
 */
public class 两数之和IV输入BST_653 {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        } else {
            return false;
        }
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (set.contains(k - node.val)) {
                return true;
            } else {
                set.add(node.val);
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return false;
    }

    @Test
    public void testFindTarget () {
        TreeNode node5 = new TreeNode(7);
        TreeNode node4 = new TreeNode(4);
        TreeNode node3 = new TreeNode(2);
        TreeNode node2 = new TreeNode(6, null, node5);
        TreeNode node1 = new TreeNode(3, node3, node4);
        TreeNode root = new TreeNode(5, node1, node2);
        int k = 28;
        System.out.println(findTarget(root, k));
    }
}
